package com.sukaiyi.leetcode._523continuous_subarray_sum;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.IntStream;
import java.util.stream.Stream;

import static org.junit.jupiter.api.Assertions.*;

/**
 * 连续的子数组和
 * <p>
 * 给定一个包含非负数的数组和一个目标整数 k，编写一个函数来判断该数组是否含有连续的子数组，其大小至少为 2，总和为 k 的倍数，即总和为 n*k，其中 n 也是一个整数
 *
 * @author sukaiyi
 * @date 2020/04/30
 * @see <a href="https://leetcode-cn.com/problems/continuous-subarray-sum/>题目地址</a>
 */
public class Solution {

    @Test
    public void test() {
        assertTrue(checkSubarraySum(new int[]{5, 0, 0}, 0));
        assertFalse(checkSubarraySum(new int[]{0, 1, 0}, 0));
        assertTrue(checkSubarraySum(new int[]{23, 2, 4, 6, 7}, 6));
        assertTrue(checkSubarraySum(new int[]{23, 2, 6, 4, 7}, 6));
        assertFalse(checkSubarraySum(new int[]{23, 2, 6, 4, 7}, 0));
        assertFalse(checkSubarraySum(new int[]{0}, 0));
    }

    public boolean checkSubarraySum(int[] nums, int k) {
        return checkSubarraySum(nums, nums.length, k);
    }

    public boolean checkSubarraySum(int[] nums, int length, int k) {
        if (length <= 1) {
            return false;
        }
        if (length == 2) {
            int s = nums[0] + nums[1];
            return k == 0 ? s == 0 : s % k == 0;
        }
        // 如果不要最后一个数，能否组成k的整数倍
        boolean ifExcludeLast = checkSubarraySum(nums, length - 1, k);
        if (ifExcludeLast) {
            return true;
        }
        // 如果要最后一个数，能否组成k的整数倍
        int sum = 0;
        for (int i = length - 1; i >= 0; i--) {
            sum += nums[i];
            if ((k == 0 ? sum == 0 : sum % k == 0) && length - i >= 2) {
                return true;
            }
        }
        return false;
    }

}
